package cn.com.algorithm.常用排序;

/**
 * 1、先对比
 * 2、在移动数组留出空位
 * 3、将对比后的值插入到空位
 */
public class 插入排序 {

    public static void insertsort(int arr[]) {

        // 从第一个元素开始循环
        for (int i = 1; i < arr.length; i++) {
            if (arr[i - 1] > arr[i]) { // 前一个元素大于后一个元素进行插入排序
                int temp = arr[i]; // 获取当前元素
                int j;
                for (j = i - 1; j >= 0 && arr[j] > temp; j--) {
                    arr[j + 1] = arr[j]; // 将数组元素后移
                }
                arr[j + 1] = temp; // 将当前元素插入到空出位置
            }
        }
    }

    public static void main(String[] args) {
        int array[] = {4, 2, 1, 5};

        System.out.println("排序之前：");
        for (int element : array) {
            System.out.print(element + " ");
        }

        insertsort(array);
        System.out.println("\n排序之后：");
        for (int element : array) {
            System.out.print(element + " ");
        }
    }
}
